/* 将一个单链表{a1, b1, a2, b2 ... an, bn}拆分成{a1, a2 ... an}和{bn, bn-1 ... b1} */

#include <iostream>
#include "headfun.h"
using namespace std;

// 拆分链表
Linklist create(LNode *&A)
{
  // 初始化B链表
  LNode *B = new LNode;
  B->next = NULL;
  
  // 辅助指针
  LNode *ra = A;
  LNode *p = A->next;
  LNode *q;
  A->next = NULL;
  
  // 遍历链表
  while (p != NULL)
  {
    // 添加进A链表
    ra->next = p;
    ra = p;
    
    // 下一个结点
    p = p->next;
    q = p;
    
    // 下一个结点
    if (q == NULL)
      break;
    p = p->next;
    
    // 头插法
    q->next = B->next;
    B->next = q;
  }
  
  // A链表最后指向空
  ra->next = NULL;
  return B;
}

int main()
{
  // 创建链表
  LNode *A = head_Linklist();
  
  // 拆分链表
  LNode *B = create(A);
  
  // 遍历两链表并打印
  LNode *q = A->next;
  LNode *p = B->next;
  
  cout << "A链表：";
  while (q != NULL)
  {
    cout << q->data << " ";
    q = q->next;
  }
  
  cout << "B链表：";
  while (p != NULL)
  {
    cout << p->data << " ";
    p = p->next;
  }
  return 0;
}